1. Field of the Invention
The present invention relates to an apparatus and method for discarding invalid pixels in a 3D computer graphic system, particularly to an apparatus and method for discarding the invalid pixels using pipelined bubble squeezing in the 3D computer graphic system.
2. Description of the Related Art
It is complicated to generate a correct 3D graphic image and display it on the screen of a monitor. A lot of processes coopeerate with each other to the resulting image on the screen. For example, there is a setup process for initialization, a rasterization process for deriving a pixel coordinate, a shading process for generating smooth colors, a texture mapping process for generating the texture structure of a surface, an alpha blending process for generating transparency and translucence effects. There are many tests responsible for checking the validity of incoming pixels during a graphic rendering process. That is, if a pixel does not pass all the validity tests and is deterrmned to be invalid, then the pixel will be discarded. On the contrary, if a pixel passes all the validity tests and be considered a valid one, then the pixel will be pushed into a frame buffer. Therefore, the validity tests determine whether a pixel is going to be rendered or discarded.
The commonly adopted validity tests including a scissor test, an alpha test, a stencil test and a depth test. The scissor test is used to classify whether a pixel is inside or outside a specific view port or a rectangular window on the screen. If a pixel lies inside the rectangle window, it means the pixel passes the scissor test and then be drawn within the rectangle window. The alpha test compares the alpha value of an inconing pixel with a reference alpha value which was defined as a threshold for accepting or rejecting an incoming pixel. The stencil test compares a reference value of an input pixel with a value stored in a stencil buffer which can be modified according to some specific stencil operations. Depending on stencil testing results, the incoming pixel will be accepted or rejected. The depth test is probably the most commonly used technique to remove a hidden surface during a rendering process. A depth value of the incoming pixel is compared to a corresponding depth value stored in the depth buffer. Based on testing results, the incoming pixel is either accepted and drawn on the screen later or rejected because the incoming pixel is hidden behind an object. The depth value in the depth buffer is updated by the depth value of the incoming pixel if the incoming pixel passes the depth test.
Currently, the pixels are determined to be shown on the screen during the rendering process of the 3D computer graphic system, depending on the results of the validity tests. However, even only one invalid pixel is found and discarded later, at least one memory access is performed and thus a lot of system resources are wasted. Therefore, if we can discard the invalid pixels before the rendering process, then a lot of unnecessary memory accesses will be saved to eliminated to enhance the system performance. The present invention proposes an apparatus and a method for sequeezing pipelined bubbles to sort a set of pixels into a valid group and an invalid group according to the results of validity tests. According to the present invention, only the valid group is considered during a rendering process. The present invention is useful in speeding up a 3D computer graphic process.
The object of the present invention is to eliminate the drawback of the low efficiency caused by an unnecessary memory access in the current 3D rendering process. To this end, the present invention provides a simplified and expandable pipelined bubble squeezer and a method for solving the above drawback. The pipelined bubble squeezer uses nxc3x97n cells to construct an interconnection network. After the validity tests, n indication bits are input in parallel to the interconnection network, and the logic value of the indication bits are sorted into continuous logic 1""s and logic 0""s. The interconnection network includes n buffer cells of the 0-th stage, and nxc3x97(nxe2x88x921) multiplexing cells between the first stage to the (nxe2x88x921)th stage. Each one of the plurality of buffer cells is constructed by a buffer only or a buffer plus a D flip flop. Each one of the plurality of multiplexing cells is constructed by a multiplexer or a multiplexer plus a D flip flop. The multiplexing cells uses a control algorithm of selecting signals or xe2x80x9cvalid bitxe2x80x9d to pass datum upwards to a cell of the next stage or pass datum rightwards to a cell of the next stage. At every stage, the indication bits which are logic 1 are input in parallel to the interconnection network and move upwards one row, like a floating bubble. Moreover, the structure of the pipelined bubble squeezer is so regular that the structure can be expanded or abridged according to the number of the pixels processed at one time.